package com.buddy.learn.algorithm.simple;

/**
 * 二分查找
 *
 * @author Buddy
 * @date 2021/4/20
 */
public class _二分查找 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6, 7, 8, 9, 10, 11};

        System.out.println("二分查找查找指定值：" + search(arr, 11));
        System.out.println("用二分查找找到 <= 的最大值：" + searchMaxLower(arr, 11));
        for (int i = 0; i < 14; i++) {
            System.out.println("用二分查找找到 >=" + i + " 的最小值：" + searchMinUpper(arr, i));
            System.out.println("用二分查找找到 >=" + i + " 的最小值：" + searchMinUpper2(arr, i));
        }
    }


    /**
     * 查找 target 的位置，找不到则返回-1
     *
     * @param arr    数组
     * @param target 目标值
     * @return 返回位置
     */
    private static int search(int[] arr, int target) {
        if (null == arr || arr.length == 0) {
            return -1;
        }
        int left = 0, right = arr.length - 1, mid;
        // 注意这里的判断条件，是必须允许 left = right 的情况存在的
        // 因为可能会出现刚好到最后左边指针到右边指针只有1个元素，而且这个元素恰恰就是我们想找的
        while (left <= right) {
//            mid = (left + right) / 2;
            // >> 1 代表除2；<<1 代表*2
            mid = left + ((right - left) >> 1);
            if (arr[mid] == target) {
                //如果mid元素已经是 target 了，那么直接返回
                return mid;
            } else if (arr[mid] > target) {
                // 查找左边的
                right = mid - 1;
            } else {
                // 查找右边的
                left = mid + 1;
            }
        }
        //如果没有找到指定的值，那么直接返回-1
        return -1;
    }


    /**
     * 思路：如果mid元素是小于或等于k，往右找，如果大于k，往左边找，直到找到一个值，最接近与目标的。
     * [1,2,3,4, <-| ,6,7]
     *
     * @param arr    数组
     * @param target 目标值
     * @return <= target 的最大值
     */
    private static int searchMaxLower(int[] arr, int target) {
        int left = 0, right = arr.length - 1, mid;
        while (left < right) {
            mid = (left + right + 1) / 2;
            if (arr[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        if (arr[left] > target) {
            return -1;
        }
        return arr[left];

    }

    /**
     * 查找大于等于的最小值
     * [1,2,3,4, |-> ,6,7,8]
     *
     * @param arr    数组
     * @param target 目标值
     * @return >= 的最小值
     */
    private static int searchMinUpper(int[] arr, int target) {
        int left = 0, right = arr.length - 1, mid;
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (arr[right] >= target) {
            return arr[right];
        } else {
            return -1;
        }
    }

    private static int searchMinUpper2(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left < arr.length - 1 && arr[left] >= target) {
            return arr[left];
        } else {
            return -1;
        }
    }
}
